package cn.kuick.match2.test3;

import java.util.ArrayList;
import java.util.Stack;

public class CombinationSum {
	
	public static boolean isMatch(Stack<Integer> sb, int target) {
		int sum = 0;
		
		for(int i=0; i<sb.size(); i++) {
			sum += sb.get(i).intValue();
		}
		
		return sum == target;
	}
	
	public static boolean isOk(Stack<Integer> sb, int target) {
		int sum = 0;
		
		for(int i=0; i<sb.size(); i++) {
			sum += sb.get(i).intValue();
		}
		
		return sum < target;
	}
	
	public static void innerOutput(int i, int[] mid, int target, ArrayList<Integer[]> output, Stack<Integer> sb) {
		for(int j=0; j<mid.length; j++) {
			int num = mid[j];
			
			sb.add(num);
			
			if (isMatch(sb, target)) {
				output.add(sb.toArray(new Integer[sb.size()]));
			} else {
				if (isOk(sb, target)) {
					innerOutput(i + 1, mid, target, output, sb);
				}
			}
			
			sb.pop();
		}
	}
	
	public static ArrayList<Integer[]> handle(int[] nums, int target) {
		ArrayList<Integer[]> output = new ArrayList<>();
		
		Stack<Integer> sb = new Stack<>();
		innerOutput(0, nums, target, output, sb);
		
		return output ;
	}
	
	public static void main(String[] args) {
		int[] input = {2, 4, 6};
		int target = 10;
		
		ArrayList<Integer[]> output = handle(input, target);
		
		for(int i=0; i<output.size(); i++) {
			Integer[] out = output.get(i);
			
			System.out.print("(");
			
			for(int j=0; j<out.length; j++) {
				if (j == out.length - 1) {
					System.out.print(out[j]);
				} else {
					System.out.print(out[j] + ",");
				}
			}
			
			System.out.println(")");
		}
	}
}
